1. Technical Field of the Invention
The present invention relates generally to the field of data communications error correction and, in particular, to a method and apparatus for decoding shortened fire codes using error trapping.
2. Description of Related Art
Conventional high-speed data communications systems commonly use cyclic redundancy check (CRC) error detection codes to detect and correct received data transmission errors. These errors can be caused by numerous transmission disturbances, such as fading, channel noise or signal interference (e.g., from frequency co-use or jamming).
A particular cyclic code error detection and correction scheme is disclosed in U.S. Pat. No. 5,381,423 to Turco ("Turco"). Turco discloses that a certain class of cyclic codes (known as "Fire Codes") can be used to systematically correct burst errors in transmission channels. A "burst error" is a long sequence of error symbols delimited on either end by non-zero error values. Here, a zero error value is used to denote the absence of an error.
Mathematically, a codeword polynomial can be used to represent the information to be transmitted (information word) and the Fire Code. For example, a generator polynomial for a Fire Code can be expressed as follows: EQU g(X)=(1+X.sup.2t-1)p(X) (1)
where t is defined as the burst correction capability of the Fire Code, and p(X) is an irreducible polynomial. The term .rho. ("rho") is defined as the period of p(X). In other words, .rho. is the smallest integer, such that p(X) divides (X.sup..rho. +1). Also, t is a positive integer, such that the expression (2t-1) is not divisible by .rho.. The length, n, of the Fire Code (number of bits in each Fire Code word) is the least common multiple of the expressions (2t-1) and .rho.. Notably, the expression (X.sup.n +1) is divisible by the Fire Code generator polynomial, g(X).
The information word (e.g., k information bits) to be transmitted can be expressed as a polynomial of degree (k-1). If the expression {u.sub.0, . . . , u.sub.k-1 } represents the bits in the information word, then the information word polynomial can be represented by: EQU u(X)=u.sub.0 +u.sub.1 X+ . . . +u.sub.k-1 X.sup.k-1. (2)
Given all of the above, a codeword polynomial, c(X), to be transmitted can be represented by: EQU c(X)=X.sup.n-k u(X)+f(X), (3)
where EQU f(X)=X.sup.n-k u(X)modg(X). (4)
From equations 3 and 4, it is evident that: EQU c(X)=0modg(X). (5)
In an exemplary operational setting, a codeword, c(X), is transmitted as a burst over a communications channel. Assuming that a burst error has occurred during the transmission, a corrupted version of the transmitted codeword is received at the channel receiver. The received codeword, r(X), can be represented by the expression: EQU r(X)=c(X)+e(X), (6)
where e(X) is an error bit pattern. The received codeword, r(X), can be considered as a single polynomial from which a single syndrome can be computed by shifting the received word in one direction, and errors can be corrected by shifting the received word in the opposite direction. The syndrome of the received word can be represented by the expression: EQU s(X)=r(X)modg(X)=e(X)modg(X). (7)
Consequently, as illustrated by equation 7, the syndrome of the received word depends on the error bit pattern in the received word.
A device commonly used for burst error correction is known as an error-trapping decoder. Its operation is based on the premise that, for some amount of cyclic shifting of the received word, the error in the burst can be isolated down to the final t bits of the syndrome. So, in accordance with that premise, an error-trapping decoder operates as follows.
For each cyclic shift of a received word, the decoder calculates a syndrome for the word. When the decoder determines that the first n-k-t bits of the syndrome are zero, the last t bits of the syndrome represent the burst error that occurred in the shifted, received word. Errors are then corrected by shifting the received word by the corresponding number of bits in the reverse direction.
Existing error-trapping decoders commonly use "left cyclic shifting" to decode received words. Mathematically, the left cyclic shift of a received word, r(X), of length n, can be expressed as: EQU r.sup.(1) (X)=Xr(X)mod(X.sup.n +1). (8)
In terms of its syndrome, s(X), the received word r(X) can be expressed as: EQU r(X)=a(X)g(X)+s(X) (9)
for some value of the term, a(X). Consequently, the syndrome, s.sup.(1) (X), for the left cyclic-shifted received word, r.sup.(1) (X), can be derived as follows: EQU s.sup.(1) (X)=r.sup.(1) (X)modg(X) (10) EQU =Xr(X)mod(X.sup.n +1)modg(X) (11) EQU =Xr(X)modg(X) (12) EQU =(Xa(X)g(X)+Xs(X))modg(X) (13) EQU =Xs(X)modg(X) (14)
Equation 12 can be derived as shown, because the expression (X.sup.n +1) is divisible by g(X). Notably, as demonstrated above, the error-trapping decoder can determine the syndrome of the left cyclic-shifted received word by using just the syndrome of the received word. This principle is used for correcting burst errors in existing error-trapping decoders.
In many burst error correction applications, the overall length of the Fire Code word and information word (n+k) obtained using standard Fire Codes can be inappropriate, because the resulting words are often too long for practical systems. Consequently, shortened versions of code words are used. In order to shorten a Fire-Coded word for transmission, some of the information bits are set to zero, the parity bits are located, and only the non-zeroed information bits and parity bits are transmitted. By setting 1 information bits to zero from the (n, k) word combination, and not transmitting these 1 information bits, the (n, k) Fire-Coded word can be shortened to an (n-1, k-1) coded word. The transmitter and receiver agree that these 1 bits will always be zero.
For example, using the European Global System for Mobile Communications (GSM) protocol, a standard Fire-Coded word of length (3014633, 3014593) can be shortened to a length (224, 184). This shortened codeword can be used to correct all burst errors of length 12 bits or less.
In reality, the (224, 184) Fire Code is merely the longer (3014633, 3014593) Fire Code with zeros substituted for the least significant 3014409 information bits. Alternatively, a representation of the information may be described as: EQU u(X)=X.sup.3014409 (u.sub.0 +u.sub.1 X+u.sub.2 X.sup.2 + . . . +u.sub.183 X.sup.183) (15)
Conceptually, these 3014409 least significant bits with a value of zero, are the first bits to be shifted into the decoder's polynomial division circuit (e.g., see FIG. 2 below). However, since the expression 0modg(X)=0, this operation is not explicitly necessary, and the actual information bits are shifted into the polynomial division circuit, as well as into the channel. When all 184 bits are shifted into the polynomial division circuit, the remainder of the division process gives the parity polynomial p(X). These parity bits follow the information bits into the channel.
FIGS. 1A and 1B illustrate two conventional bit configurations that are used to encode shortened Fire-Coded words. In the configuration shown in FIG. 1A, the information bits and parity bits are contiguous. In the configuration shown in FIG. 1B, the information bits and parity bits are not contiguous. The dummy information bits are not transmitted. The configuration shown in FIG. 1A is preferred over the configuration shown in FIG. 1B, because the configuration in FIG. 1B may separate burst errors that occur in the transmission into two shorter burst errors, which the decoder in the receiver may not be equipped to handle.
In the case of FIG. 1B, the zero bits will be explicitly shifted into the channel, or the parity bits will be computed indirectly using other polynomial algebra techniques, but which increases the number of operations required in the encoding circuitry.
An error-trapping decoder can also be used to decode a shortened Fire-Coded word, by assuming that the first information bits being received and decoded are zero and error-free. However, a problem arises with that decoding scheme, because the decoder must left-shift the received coded word a substantial number of times before the error burst portion of the code word is encountered. In fact, the number of such shifts needed is on the order of the length of an unshortened coded word. Consequently, for a standard GSM codeword, about 3 million left-shift operations would be required, which significantly increases error correction delays and thereby reduces data throughput.
One solution to this problem is described in the textbook: "Error Control Coding: Fundamentals and Applications" by S. Lin and D. Costello, Prentice Hall, Inc., Englewood Cliffs, N.J., 1983. It is recognized that the problem arises from the process of calculating the syndrome of a left cyclical shift of the received codeword by 1 bits. In other words, the syndrome for decoding a received bit, r.sub.n-1-1, is equal to the remainder resulting from the division of the expression X.sup.n-k+1 r(X) by the generator polynomial, g(X), as illustrated by the following equation: EQU X.sup.n-k-l r(X)=a.sub.1 (X)g(X)+s.sup.(n-k-l) (X). (16)
Equation 16 infers that premultiplying r(X) can yield the desired syndrome, as illustrated by the expression: EQU .rho.(X)r(X)=a.sub.1 (X)+a.sub.2 (X)r(X)!g(X)+s.sup.(n-k-l) (X).(17)
The premultiplication factor, .rho.(X), is given by: EQU .rho.(X)=X.sup.n-k-l +a.sub.2 (X)g(X). (18)
Equation 18 infers that the syndrome, s.sup.(n-k-1) (X) can be obtained by using polynomial logic circuitry that implements the expression, .rho.(X)r(X)/g(X). However, a substantial amount of relatively complex hardware is required to implement such a scheme.
A similar result may be obtained by representing the division operation described directly above in terms of reciprocal polynomials. For example, starting with the following expression for the received codeword: EQU r(X)=a(X)g(X)+s(X), (19)
the reciprocal of r(X) can be described as follows: EQU X.sup.n r(X.sup.-1)=X.sup.k-1 aX.sup.-1)!X.sup.n-k+1 g(X.sup.-1)!+X.sup.n-k s(X.sup.-1)!X.sup.k. (20)
Note that equation 20 describes the reciprocal cyclic code: EQU r'(X)=a'(X)g'(X)+X.sup.k s'(X). (21)
Therefore, the syndrome of the reciprocal cyclic code, r' (X), can be described in terms of the syndrome of the received word, by the expression : EQU .nu.(X)s'(X)modg'(X), (22)
whereby the pre-multiplier term, .nu.(X), is equal to the expression: (X.sup.k mod g'(X)). However, similar to the result obtained from implementing circuitry suggested by the article disclosed above, a substantial amount of relatively complex hardware is also required to implement this scheme.